package org.example.myleet.dynamic;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;
import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class DynamicProgrammingSolution {

    //p5
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] charArr = s.toCharArray();
        //表示palindromeLengths[i][j]表示从左往右看即j到i是否回文
        boolean[][] palindrome = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            //初始化，每个字符本身是回文
            palindrome[i][i] = true;
        }
        int maxPalindromeLength = 1;
        StringBuilder sb = new StringBuilder();
        sb.append(charArr[0]);
        for (int i = 1; i < n; ++i) {
            //动态规划，从i位置开始向左拓展长度查看字符串是否为回文
            for (int j = i - 1; j >= 0; --j) {
                //从i位置向左延伸
                if (charArr[j] == charArr[i]) {
                    //遇到j和i的字符相同，讨论是否回文
                    //如果j到i的距离为1或2，那么都可以形成回文，例如aa和aba
                    //如果[j + 1]到[i - 1]位置的字符已经是回文，而且j字符==i字符，说明j到i也是回文，例如(j)a(j+1)bab(i-1)a(i)
                    if (i - j < 3 || palindrome[i - 1][j + 1]) {
                        palindrome[i][j] = true;
                        int len = i - j + 1;
                        if (maxPalindromeLength < len) {
                            //回文长度刷新，更新最长回文子串结果
                            maxPalindromeLength = len;
                            sb.delete(0 ,sb.length());
                            for (int k = j; k <= i; ++k) {
                                sb.append(charArr[k]);
                            }
                        }
                    }
                }
            }
        }
        return sb.toString();
    }

    /**
     * LCP 07【动态规划】传递信息
     * 先预处理接收者能够收到信息的来源的所有发送者
     * 状态推导为：下一轮某个接收者能够收到信息的方案数等于来自上一轮中信息到达的接收者的方案树之和
     * dp[round][receiver] = sum(dp[round - 1][sender])
     */
    public int numWays(int n, int[][] relation, int k) {
        Map<Integer, Set<Integer>> receiverToSendersMap = new HashMap<>();
        for (int[] r : relation) {
            Set<Integer> senders = receiverToSendersMap.getOrDefault(r[1], new HashSet<>());
            senders.add(r[0]);
            receiverToSendersMap.put(r[1], senders);
        }
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int round = 1; round <= k; ++round) {
            for (int receiver = 0; receiver < n; ++receiver) {
                Set<Integer> senders = receiverToSendersMap.getOrDefault(receiver, Collections.EMPTY_SET);
                for (Integer sender : senders) {
                    dp[round][receiver] += dp[round - 1][sender];
                }
            }
        }
        return dp[k][n - 1];
    }

    //p10
    /**
     * 5 ms
     * 动态规划
     */
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i=0; i<=s.length(); i++) {
            //0位置开始，代表s为空的情况
            for (int j=1; j<=p.length(); j++) {
                if (matches(s, p, i, j)) {
                    //si匹配pi，状态从上一个匹配情况传递过来
                    dp[i][j] = dp[i-1][j-1];
                } else if ('*' == p.charAt(j-1)) {
                    //*号可以匹配1个或0个，如果此时i=0，si为空字符，也可以匹配上
                    dp[i][j] = dp[i][j-2];
                    if (matches(s, p, i, j-1)) {
                        //如果si的上一个字符si-1可以匹配上，就匹配上，否则X*认为匹配0个，直接传递dp[i][j-2]的状态
                        dp[i][j] = dp[i - 1][j] || dp[i][j-2];
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
    private boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            //还没开始匹配s
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            //匹配任意字符，可以匹配
            return true;
        }
        //字符相同，匹配
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

    //剑指Offer 42
    public int maxSubArray(int[] nums) {
        int dp = nums[0], max = dp;
        for (int i = 1; i < nums.length; ++i) {
            int dpi = Math.max(nums[i], dp + nums[i]);
            dp = dpi;
            max = Math.max(max, dpi);
        }
        return max;
    }

    //62【动态规划】不同路径
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[n][m];
        for (int i = 0; i < m; ++i) {
            //第一列的格子上，从上往下走，每一格都只有一种路径到达
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; ++j) {
            //第一行的格子上，从左往右走，每一格都只有一种路径到达
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                //到达每一格时，机器人只能从该格子的上面一格或左边一格走过来，所以dp[i][j]格子的路径数量等于这两条路径的数量之和
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        //到达最右下角的格子即为路径数量答案
        return dp[m - 1][n - 1];
    }

    //70【动态规划】爬楼梯
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            //爬楼梯可以是一级或两级，也就是一级之前和两级之前的方法数总和
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }

    /**
     * 91【动态规划】解码方法
     * 1 ms
     * 动态规划，经过推敲，其变化规律类似于斐波那契数列，F(n) = F(n-1) + F(n-2)
     * 讨论如下：
     * 1、第n位数与第n-1位数是可以合起来解码的（例如112，1与2可以结合解码），此时最后的12有两种情况，既可以看成一个整体12，也可以看成1和2
     * 如果看成12，则解码数与第1位的"1"相同；如果看成1和2，则解码数与第2位的"1"相同。因此112的解码数就是第1位的"1"与第2位的"1"解码数之和
     * 符合F(n) = F(n-1) + F(n-2)
     * 2、第n位数与第n-1位数不可以合起来解码的（例如132，3与2不可以结合解码，因为32 > 26，超出解码范围；或1103，03不能解码，只能解码10和3）
     * 此时最后的2的解码数与前面的3相同
     * 符合F(n) = F(n-1)
     * 3、第n位数是0，如果能解码都只能结合n-1位数解码（例如1120，只能解码20；例如1130，直接不能解码，30不能解码），此时若能解码，0必须与前面n-1的数一起解码
     * 因此解码数与n-2位的解码数相同
     * 符合F(n) = F(n-2)
     */
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        //dp_i_2既F(n-2)，dp_i_1既F(n-1)，dp既F(n)
        int n = s.length(), dp_i_2 = 1, dp_i_1 = 1, dp = 1;
        for (int i = 1; i < n; ++i) {
            char c = s.charAt(i);
            char cLast = s.charAt(i - 1);
            if (c == '0') {
                //情况3
                if (cLast != '2' && cLast != '1') {
                    //不是10或20，就不能解码，gg
                    return 0;
                } else {
                    //情况3，能解码，必须与前一位一起解码，看成一个整体，这个整体相当于叠在i-2位之后，因此解码数和i-2相同
                    dp = dp_i_2;
                }
            } else {
                if (cLast == '0') {
                    //情况2
                    dp = dp_i_1;
                } else {
                    //计算i-1位与i位组成的code，如果小于等于26，说明能解码，否则不能组合起来解码，只能单独解码
                    int code = (cLast - '0') * 10 + (c - '0');
                    if (code <= 26) {
                        //情况1
                        dp = dp_i_1 + dp_i_2;
                    } else {
                        //情况2
                        dp = dp_i_1;
                    }
                }
            }
            //动态规划状态转移
            dp_i_2 = dp_i_1;
            dp_i_1 = dp;
        }
        return dp;
    }

    /**
     * 115【动态规划】不同的子序列
     * 4 ms
     */
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        //dp[i][j]代表字符串t的前i个字符在字符串s的前j个字符中匹配的次数
        int[][] dp = new int[n+1][m+1];
        for (int j=0; j<m+1; ++j) {
            //当n=0时，即空字符串与每一个s的连续子串都匹配，都是1
            dp[0][j] = 1;
        }
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j) {
                //递推公式，求第i+1，j+1的情况
                if (t.charAt(i) == s.charAt(j)) {
                    //当t的第i个字符与s的第j个字符匹配时，匹配结果相当于t在i-1字符，s在j-1字符时，t字符串延伸了1个字符，因此是dp[i-1][j-1] + dp[i][j-1]
                    dp[i+1][j+1] = dp[i][j] + dp[i+1][j];
                } else {
                    //否则就没变，状态直接转移到下一个字符串位置
                    dp[i+1][j+1] = dp[i+1][j];
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 118【动态规划（直接简单）】杨辉三角
     * 根据行数生成杨辉三角
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> tri = new ArrayList<>();
        if (numRows < 1) {
            return tri;
        }
        List<Integer> row1 = new ArrayList<>();
        row1.add(1);
        tri.add(row1);
        if (numRows == 1) {
            return tri;
        }
        for (int i=2; i<=numRows; i++) {
            List<Integer> prevRow = tri.get(i-2);
            List<Integer> row = new ArrayList<>();
            for (int j=0; j<i;j++) {
                int prevLeft = j-1 > -1 ? prevRow.get(j-1) : 0;
                int prevRight = j < prevRow.size() ? prevRow.get(j) : 0;
                row.add(prevLeft + prevRight);
            }
            tri.add(row);
        }
        return tri;
    }

    /**
     * 119【动态规划（直接简单）】杨辉三角 II
     * 1 ms
     * 复制上一行，用上一行填充这一行，反复这个过程
     * 空间复杂度O(rowIndex)
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> reply = new ArrayList<>();
        if (rowIndex == 0) {
            reply.add(1);
            return reply;
        }
        int[] prev = new int[rowIndex+1];
        prev[0] = 1;
        int[] next = new int[rowIndex+1];
        for (int i=1; i<rowIndex+1; i++) {
            next = new int[rowIndex+1];
            next[0] = 1;
            for (int j=1; j<rowIndex+1; j++) {
                next[j] = prev[j-1] + prev[j];
            }
            prev = next;
        }
        for (int i=0; i<rowIndex+1; i++) {
            reply.add(next[i]);
        }
        return reply;
    }

    /**
     * 120【动态规划】三角形最小路径和
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dpThisLine = new int[n];
        dpThisLine[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            List<Integer> line = triangle.get(i);
            dpThisLine[i] = dpThisLine[i - 1] + line.get(i);
            for (int j = i - 1; j > 0; --j) {
                //空间优化一半的情况，需要从后面往前面遍历进行选择
                dpThisLine[j] = Math.min(dpThisLine[j], dpThisLine[j - 1]) + line.get(j);
            }
            dpThisLine[0] = dpThisLine[0] + line.get(0);
        }
        int min = Integer.MAX_VALUE;
        for (Integer x : dpThisLine) {
            min = Math.min(min, x);
        }
        return min;
    }

    /**
     * 122【动态规划】买卖股票的最佳时机 II
     */
    public int maxProfit122(int[] prices) {
        int EMPTY = 0;
        int BOUGHT = 1;
        //status代表持有的总资产，status[i][0]表示第i天不持有股票的总资产, status[i][1]表示第i天持有股票的总资产
        int[][] status = new int[prices.length][2];
        int day = 0;
        //第1天不动时，总资产为0，初始化状态
        status[day][EMPTY] = 0;
        //如果第1天买入，相当于借了钱买入
        status[day][BOUGHT] = -prices[day];
        while (day < prices.length - 1) {
            ++day;
            //当天空仓时可能来自前一天空仓，也可能是昨天持有按今天的价格把持有的股票卖掉（得钱），比较哪一种更赚，挑赚的那一种作为今天空仓时资产状态
            status[day][EMPTY] = Math.max(status[day-1][EMPTY], status[day-1][BOUGHT] + prices[day]);
            //当天持有可能来自前一天持有，也可能时昨天空仓今天按今天的价格买入（减钱），比较哪一种更赚，挑赚的那一种作为今天持有的资产状态
            status[day][BOUGHT] = Math.max(status[day-1][BOUGHT], status[day-1][EMPTY] - prices[day]);
        }
        //最后一天空仓时的结果就是最赚的
        return status[day][EMPTY];
    }

    /**
     * 123【动态规划】买卖股票的最佳时机 III
     * 29 ms
     */
    public int maxProfit123(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        //0-buy1, 1-sell1, 2-buy2, 3-sell2
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i=1; i<prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]);
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
        }
        return Math.max(dp[prices.length-1][1], dp[prices.length-1][3]);
    }

    /**
     * 132【动态规划】分割回文串 II
     * 17 ms
     */
    public int minCut(String s) {
        int n = s.length();
        //初始化所有子串的回文情况
        boolean[][] palindrome = new boolean[n][n];
        for (int i=0; i<n; i++) {
            Arrays.fill(palindrome[i], true);
        }
        for (int i=n-1; i>=0; --i) {
            for (int j=i+1; j<n; ++j) {
                //利用动态规划预处理所有子串的回文情况
                //从结尾开始，逐步扩大子串范围，[i+1][j-1]如果是回文，只要两端新拼接的i和j字符相同则新子串也是回文
                palindrome[i][j] = s.charAt(i) == s.charAt(j) && palindrome[i+1][j-1];
            }
        }
        //利用动态规划推导结果，想要知道dp[0..i]的分割次数，可以从dp[0..j]推导出来，必须满足[j..i]是回文子串，则dp[0..i] = dp[0..j] + 1
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i=1; i<n; i++) {
            if (palindrome[0][i]) {
                dp[i] = 0;
            }
            for (int j=i; j>0; j--) {
                if (palindrome[j][i]) {
                    dp[i] = Math.min(dp[i], dp[j-1] + 1);
                }
            }
        }
        return dp[n-1];
    }

    /**
     * 188【动态规划】买卖股票的最佳时机 IV
     * 2 ms
     * 参考lippon的《Java 动态规划 清晰简明》
     */
    public int maxProfit(int k, int[] prices) {
        if (k == 0 || prices.length < 2) {
            return 0;
        }
        if (k > (prices.length / 2)) {
            //超过交易天数一半以上的交易次数忽略，没用，因为最多只能完成交易天数一半的交易次数
            k = prices.length / 2;
        }
        //持有状态及交易次数相关的资产
        int[][] dp1 = new int[prices.length][k+1];
        //空仓状态及交易次数相关的资产
        int[][] dp2 = new int[prices.length][k+1];
        for (int i=0; i<=k; i++) {
            //第一天收市时持仓状态，初始化
            dp1[0][i] = -prices[0];
        }
        for (int i=1; i<prices.length; i++) {
            for (int j=0; j<=k; j++) {
                //遍历所有可能的交易次数
                if (j < k) {
                    //空仓状态可能来自前一天持仓卖出（交易次数比比今天多1），也可能来自前一天保持空仓（交易次数不变）
                    dp2[i][j] = Math.max(dp1[i - 1][j + 1] + prices[i], dp2[i - 1][j]);
                } else {
                    //j == k，说明没有交易
                    dp2[i][j] = dp2[i-1][j];
                }
                //持仓状态可能来自前一天持仓，也可能来自今天买入（昨天空仓状态 - 今天股价，还未算入交易次数）
                dp1[i][j] = Math.max(dp1[i - 1][j], dp2[i - 1][j] - prices[i]);
            }
        }
        int maxProfit = 0;
        for (int i=0; i<k; i++) {
            //在最后的状态中在不同的交易次数中寻找最优解
            maxProfit = Math.max(maxProfit, dp2[prices.length-1][i]);
        }
        return maxProfit;
    }

    /**
     * 198【动态规划】打家劫舍
     */
    public int rob198(int[] nums) {
        int n = nums.length;
        if (n < 2) return nums[0];
        int dp0 = nums[0];
        int dp1 = Math.max(dp0, nums[1]);
        int dpi;
        for (int i = 2; i < n; ++i) {
            dpi = Math.max(dp1, dp0 + nums[i]);
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }

    /**
     * 213【动态规划】打家劫舍 II
     * 0 ms
     * 因为题目的第一个元素与最后一个元素相连，因此进行两次动态规划，一次是用第一个不用最后一个，一次是用最后一个不用第一个，取最大的结果
     */
    public int rob213(int[] nums) {
        int n = nums.length;
        int lastMax = Integer.MIN_VALUE;
        if (n < 4) {
            for (int num : nums) {
                lastMax = Math.max(lastMax, num);
            }
            return lastMax;
        }
        //使用数组记录动态规划的各个结果，比较耗费内存，但相对来说比较容易理解
        //用第一个不用最后一个
        int[] dp1 = new int[n];
        dp1[0] = nums[0];
        dp1[1] = nums[1];
        for (int i = 2; i < n-1; ++i) {
            lastMax = Math.max(lastMax, dp1[i-2]);
            dp1[i] = Math.max(nums[i] + lastMax, nums[i] + dp1[i-2]);
            dp1[i] = Math.max(dp1[i], dp1[i-1]);
        }
        //用最后一个不用第一个
        lastMax = Integer.MIN_VALUE;
        int[] dp2 = new int[n];
        dp2[1] = nums[1];
        dp2[2] = nums[2];
        for (int i = 3; i < n; ++i) {
            lastMax = Math.max(lastMax, dp2[i-2]);
            dp2[i] = Math.max(nums[i] + lastMax, nums[i] + dp2[i-2]);
            dp2[i] = Math.max(dp2[i], dp2[i-1]);
        }
        return Math.max(dp1[n-2], dp2[n-1]);
    }

    /**
     * 256【动态规划】粉刷房子
     */
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3];
        dp[0] = costs[0];
        for (int i = 1; i < n; ++i) {
            //此房子的颜色需与上一间房子的颜色不同，0的状态只能来自于1或2，1的状态只能来自于0或2，2的状态只能来自于0或1
            dp[i][0] = Math.min(dp[i - 1][1] + costs[i][0], dp[i - 1][2] + costs[i][0]);
            dp[i][1] = Math.min(dp[i - 1][0] + costs[i][1], dp[i - 1][2] + costs[i][1]);
            dp[i][2] = Math.min(dp[i - 1][0] + costs[i][2], dp[i - 1][1] + costs[i][2]);
        }
        return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    /**
     * 279【动态规划】完全平方数
     */
    public int numSquares(int n) {
        //先找出不大于n的完全平方数power
        int numLen = 0;
        int[] pNums = new int[101];
        for (int i = 1; i <= 100; ++i) {
            int power = i * i;
            if (power <= n) {
                pNums[numLen++] = power;
            }
        }
        //dp表示在第i个完全平方数时，组成j需要多少个元素
        int[][] dp = new int[numLen][n + 1];
        for (int j = 1; j <= n; ++j) {
            //第一个完全平方数都是1，所以j是多少就需要多少个1元素
            dp[0][j] = j;
        }
        for (int i = 1; i < numLen; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j < pNums[i]) {
                    //j比第i个元素还小，则第i个元素不能选，所以j的解法继承自i-1的j
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //j比第i个元素相等或大，则第i个元素可以选也可以不选，比较不选与选的大小，取小的
                    //选择第i个元素时，元素数量应是dp[i][j - pNums[i]]，再+1
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - pNums[i]] + 1);
                }
            }
        }
        return dp[numLen - 1][n];
    }

    /**
     * 309【动态规划】买卖股票的最佳时机含冷冻期
     */
    public int maxProfit309(int[] prices) {
        int n = prices.length;
        if (n == 1) return 0;
        if (n == 2) return Math.max(0, prices[1] - prices[0]);
        //0-满仓，1-清仓冷冻期，2-清仓非冷冻期
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

    /**
     * 313【动态规划】超级丑数
     * 官方解，动态规划
     * 利用pointer数组记录每个prime对应的最新的下一个丑数
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        long[] dp = new long[n + 1];
        dp[1] = 1;
        int[] pointer = new int[primes.length];
        for (int j = 0; j < primes.length; ++j) {
            pointer[j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            long[] candidates = new long[primes.length];
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; ++j) {
                //记录一系列候选的丑数
                candidates[j] = dp[pointer[j]] * primes[j];
                //找到最小的丑数作为下一个紧跟着的丑数
                dp[i] = Math.min(dp[i], candidates[j]);
            }
            for (int j = 0; j < primes.length; ++j) {
                if (candidates[j] == dp[i]) {
                    //如果候选丑数中与最新一个丑数相同，说明此时的j代表的质数有被用到，被使用次数+1
                    ++pointer[j];
                }
            }
        }
        return (int) dp[n];
    }

    /**
     * 322【BFS】零钱兑换
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i <= amount; ++i) {
            for (int coin : coins) {
                int a = i - coin;
                if (a >= 0 && dp[a] > -1) {
                    if (dp[i] == -1) {
                        dp[i] = dp[a] + 1;
                    } else {
                        dp[i] = Math.min(dp[i], dp[a] + 1);
                    }
                }
            }
        }
        return dp[amount];
    }

    /**
     * 337【动态规划】打家劫舍 III
     */
    public int rob337(TreeNode root) {
        int[] result = dfs337(root);
        return Math.max(result[0], result[1]);
    }
    private static final int[] NULL = new int[]{0, 0};
    private int[] dfs337(TreeNode node) {
        int[] leftResult = NULL;
        if (null != node.left) {
            //寻找子问题的答案
            leftResult = dfs337(node.left);
        }
        int[] rightResult = NULL;
        if (null != node.right) {
            rightResult = dfs337(node.right);
        }
        //通过子问题的答案计算本结点的答案，分两种情况讨论。
        //1. 本结点若不选，则子结点的答案中可以选择最大的情形；
        //2. 本结点若选取，则子结点的答案只能选择子结点不选的情况。
        //返回结果中0位置存储的是不选本结点时能产生的最大答案，1位置存储的是选择本结点时能产生的最大答案
        return new int[]{Math.max(leftResult[0], leftResult[1]) + Math.max(rightResult[0], rightResult[1]), leftResult[0] + rightResult[0] + node.val};
    }

    /**
     * 354【动态规划】俄罗斯套娃信封问题
     * 271 ms
     */
    public int maxEnvelopes(int[][] envelopes) {
        //先对信封进行排序，w升序，h降序，好处是避免h形成长度超过1的严格递增的序列而导致错误
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o2[1] - o1[1];
            }
        });
        int n = envelopes.length;
        int[] encaseCount = new int[n];
        //默认所有位置都是1
        Arrays.fill(encaseCount, 1);
        int ans = 1;
        for (int i=1; i<n; i++) {
            for (int j=0; j<i; j++) {
                //遍历0～i-1位置，寻找严格递增子序列的长度，动态规划，找到i位置的对于h最长的严格递增子序列
                if (envelopes[i][1] > envelopes[j][1]) {
                    encaseCount[i] = Math.max(encaseCount[i], encaseCount[j]+1);
                }
            }
            //更新答案
            ans = Math.max(ans, encaseCount[i]);
        }
        return ans;
    }

    /**
     * 368【排序+动态规划】最大整除子集
     * 19 ms
     * 升序排序后，满足整除交换律，只要与最近的一个数整除即可加入整除子集中
     * O(nlogn + n^2)
     */
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int len = nums.length;
        //排序
        Arrays.sort(nums);
        int[] dp = new int[len];
        dp[0] = 1;
        int maxI = 0, count = 0;
        //嵌套循环用动态规划找到最大的整除子集
        for (int i = 1; i < len; ++i) {
            boolean foundDivideNumber = false;
            for (int j = i - 1; j >= 0; --j) {
                if (nums[i] % nums[j] == 0) {
                    foundDivideNumber = true;
                    if (dp[i] <= dp[j]) {
                        dp[i] = dp[j] + 1;
                        if (dp[i] > count) {
                            //出现更大的整除子集，更新最新最大的数字的下标以及对应的子集长度
                            maxI = i;
                            count = dp[i];
                        }
                    }
                }
            }
            if (!foundDivideNumber) {
                //找不到整除子集则从这个位置从新开始算
                dp[i] = 1;
            }
        }
        //初始化最大整除子集结果
        ArrayList<Integer> maxList = new ArrayList<>();
        maxList.add(nums[maxI]);
        --count;
        for (int i = maxI - 1; i >= 0; --i) {
            //从后往前遍历，满足被整除子集中最小的数字整除的数字，而且计数上表明是下一个需要加入整除子集的数字时，将这个数字加入整除子集中
            if (maxList.get(maxList.size() - 1) % nums[i] == 0 && count == dp[i]) {
                maxList.add(nums[i]);
                --count;
            }
        }
        return maxList;
    }

    /**
     * 376【动态规划】摆动序列
     * DP, O(2n)
     * 0 ms
     */
    public int wiggleMaxLength(int[] nums) {
        //先讨论特殊情况
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        if (nums.length == 2) {
            if (nums[0] == nums[1]) {
                return 1;
            }
            return 2;
        }
        //清除nums[i] == num[i-1]的情况，即连续重复的去掉
        int[] nums_ = new int[nums.length];
        nums_[0] = nums[0];
        //新数组的长度j
        int j = 1;
        for (int i=1; i<nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                nums_[j++] = nums[i];
            }
        }
        //DP最大长度的状态
        int[] maxL = new int[j];
        //DP上一个两数差值状态
        long[] lastSub = new long[j];
        //初始化0位置
        maxL[0] = 1;
        lastSub[0] = 0;
        for (int i=1; i<j; i++) {
            //当前差值
            long curSub = nums_[i] - nums_[i-1];
            if ((curSub > 0 && lastSub[i-1] <= 0) || (curSub < 0 && lastSub[i-1] >= 0)) {
                //符合摆动规则，最大长度+1，lastSub[i-1] == 0的情况只出现在第一位
                maxL[i] = maxL[i-1] + 1;
            } else {
                //不符合摆动规则，最大长度等于上一个状态传递过来
                maxL[i] = maxL[i-1];
            }
            //记录当前差值，作为下一个状态推演
            lastSub[i] = curSub;
        }
        //结束查找，最后一个位置即最大摆动长度
        return maxL[j-1];
    }

    /**
     * 377【动态规划】组合总和 Ⅳ
     * 1 ms
     * O(n^2)
     * 动态规划，以1...target中间的各个值逐渐递增为状态推导，从凑成1、2、3、4...target一直凑到target作为推导的方向
     * 例如要凑成4，则在凑成1、2、3的基础上再拼接某个数x就可以得到4，此时如果找到x，则拼接方法就等于1、2、3的拼接方法之和
     * dp代表拼接结果为i时拼接的方案数目
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        //拼接为0时只有1种方案，就是什么也不选
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int x : nums) {
                if (x <= i) {
                    //当找到一个x，满足x <= i时，说明存在一个数（i-x），这个（i-x）可以与x结合后得到i，此时dp[i]累加dp[i - x]的拼接方案数目
                    dp[i] += dp[i - x];
                }
            }
        }
        return dp[target];
    }

    /**
     * 518【DP】零钱兑换 II
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; ++i) {
                //对于面额为coin的硬币，当 coin≤i≤amount时，如果存在一种硬币组合的金额之和等于i−coin，则在该硬币组合中增加一个面额为coin的硬币，即可得到一种金额之和等于i的硬币组合。
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    /**
     * 688【动态规划】骑士在棋盘上的概率
     */
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = new int[][]{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        double[][][] dp = new double[k + 1][n][n];
        int r, c;
        dp[0][row][column] = 1.0;
        for (int step = 1; step <= k; ++step) {
            int prevStep = step - 1;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    for (int[] dir : dirs) {
                        r = i + dir[0];
                        c = j + dir[1];
                        if (0 <= r && r < n && 0 <= c && c < n) {
                            //上一步每个位置有1/8的机会跳到下一个可能的方向
                            //每个位置等于累积上一步可能跳过来的位置的概率的1/8
                            dp[step][i][j] += dp[prevStep][r][c] * 0.125;
                        }
                    }
                }
            }
        }
        double p = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                p += dp[k][i][j];
            }
        }
        return p;
    }

    /**
     * 714【动态规划】买卖股票的最佳时机含手续费
     */
    public int maxProfit(int[] prices, int fee) {
        //status代表持有的总资产，status0[0]表示前一天不持有股票的总资产, status0[1]表示前一天持有股票的总资产
        int[] status0 = new int[2];
        //第1天不动时，总资产为0，初始化状态
        status0[0] = 0;
        //如果第1天买入，相当于借了钱买入
        status0[1] = -prices[0];
        for (int day = 1; day < prices.length; ++day) {
            int[] status1 = new int[2];
            //当天空仓时可能来自前一天空仓，也可能是昨天持有按今天的价格把持有的股票卖掉（得钱，扣除手续费），贪心
            status1[0] = Math.max(status0[0], status0[1] + prices[day] - fee);
            //当天持有可能来自前一天持有，也可能时昨天空仓今天按今天的价格买入（减钱），比较哪一种更赚，挑赚的那一种作为今天持有的资产状态
            status1[1] = Math.max(status0[1], status0[0] - prices[day]);
            status0 = status1;
        }
        //最后一天空仓时的结果就是最赚的
        return status0[0];
    }

    //p799
    public double p799ChampagneTower(int poured, int query_row, int query_glass) {
        double[] row = {poured};
        for (int i = 1; i <= query_row; i++) {
            double[] nextRow = new double[i + 1];
            for (int j = 0; j < i; j++) {
                double volume = row[j];
                if (volume > 1) {
                    nextRow[j] += (volume - 1) / 2;
                    nextRow[j + 1] += (volume - 1) / 2;
                }
            }
            row = nextRow;
        }
        return Math.min(1, row[query_glass]);
    }

    //p808
    private double p808DP[][];

    public double p808SoupServings(int n) {
        if (n >= 4475) {
            //当 n≥4475 时，所求概率已经大于 0.99999 了（可以通过上面的动态规划方法求出），它和 1 的误差（无论是绝对误差还是相对误差）都小于 10^−5
            return 1;
        }
        n = (int) Math.ceil((double) n / 25);
        p808DP = new double[n + 1][n + 1];
        return p808DFS(n, n);
    }

    private double p808DFS(int a, int b) {
        if (a <= 0 && b <= 0) {
            //A、B两种汤同时分配完，贡献1/2倍的概率
            return 0.5;
        } else if (a <= 0) {
            //A先分配完，贡献1倍概率
            return 1;
        } else if (b <= 0) {
            //B先分配完，这种概率贡献为0
            return 0;
        }
        if (p808DP[a][b] == 0) {
            //4种分配方式概率相同，因此每一种分法贡献1/4倍的概率，每一种分法进行一次递归
            p808DP[a][b] = 0.25 * (p808DFS(a - 4, b) + p808DFS(a - 3, b - 1) + p808DFS(a - 2, b - 2) + p808DFS(a - 1, b - 3));
        }
        return p808DP[a][b];
    }

    //1105
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            dp[i + 1] = Integer.MAX_VALUE;
            int tierHeight = 0;
            int widthSum = 0;
            for (int j = i; j > -1; --j) {
                widthSum += books[j][0];
                if (shelfWidth >= widthSum) {
                    tierHeight = Math.max(tierHeight, books[j][1]);
                    dp[i + 1] = Math.min(dp[i + 1], dp[j] + tierHeight);
                } else {
                    break;
                }
            }
        }
        return dp[n];
    }

    //p1139
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
//        for (int i = 0; i < m; ++i) {
//            System.out.println(JsonUtils.toJson(grid[i]));
//        }
        int answer = 0, prevMaxLen = 0;
        //0-向左连续1的个数, 1-向上连续1的个数
        int[][][] dp = new int[m][n][2];
        if (grid[0][0] == 1) {
            dp[0][0][0] = 1;
            dp[0][0][1] = 1;
            answer = 1;
            prevMaxLen = 1;
        }
        for (int i = 1; i < m; ++i) {
            if (grid[i][0] == 1) {
                dp[i][0][0] = 1;
                dp[i][0][1] = dp[i - 1][0][1] + 1;
                answer = 1;
                prevMaxLen = 1;
            }
        }
        for (int j = 1; j < n; ++j) {
            if (grid[0][j] == 1) {
                dp[0][j][0] = dp[0][j - 1][0] + 1;
                dp[0][j][1] = 1;
                answer = 1;
                prevMaxLen = 1;
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (grid[i][j] == 1) {
                    dp[i][j][0] = dp[i][j - 1][0] + 1;
                    dp[i][j][1] = dp[i - 1][j][1] + 1;
                    int len = Math.min(dp[i][j][0], dp[i][j][1]);
                    if (prevMaxLen < len) {
                        for (int k = len; k > prevMaxLen; --k) {
                            if (k <= dp[i][j - k + 1][1] && k <= dp[i - k + 1][j][0]) {
                                answer = Math.max(answer, k * k);
                                prevMaxLen = k;
                                break;
                            }
                        }
                    }
                }
            }
        }
//        for (int i = 0; i < m; ++i) {
//            System.out.println(JsonUtils.toJson(dp[i]));
//        }
        return answer;
    }

    /**
     * 1155【动态规划】掷骰子等于目标和的方法数
     * 对于问题的规模缩小考虑：考虑第n个骰子分别投出x=1、2、3...k的k种情形
     * 只要考虑前(n-1)个骰子投出(target-x)的结果的方法数，即为第n个骰子投出x并得到target结果的方法数
     * 将x的k种情况累加起来就是答案
     */
    public int numRollsToTarget(int n, int k, int target) {
        int mod = 1000000007;
        //所有的中间状态（优化时可以采取滚动数组的方式，只用两个一维数组，一个是上一个状态，另一个是当前状态）
        //二维数组的每一行最大长度应为骰子面数k和target之间取最大值，因为有可能target很小但骰子的面数大
        int[][] dp = new int[n][Math.max(k, target) + 1];
        for (int x = 1; x <= k; ++x) {
            //初始化，第一个骰子
            dp[0][x] = 1;
        }
        //第r颗筛子的投掷（r从0开始到n-1）
        int r = 1;
        while (r < n) {
            int r_1 = r - 1;
            for (int i = 2; i <= target; ++i) {
                for (int x = 1; x <= k; ++x) {
                    int y = i - x;
                    if (y > 0) {
                        dp[r][i] = (dp[r][i] + dp[r_1][y]) % mod;
                    }
                }
            }
            ++r;
        }
        return dp[n - 1][target];
    }

    //p1223
    public int dieSimulator(int n, int[] rollMax) {
        int MOD = 1000000007;
        long[][] dices = new long[n][6];
        long[] sums = new long[n];
        //初始状态，骰子第一次投出的所有结果都合法，因此n=1的情况下6种结果都合法
        Arrays.fill(dices[0], 1);
        sums[0] = 6;
        for (int i = 1; i < n; ++i) {
            long sum = 0;
            for (int j = 0; j < 6; ++j) {
                //投出第i次前连续rollMax[j]的第一个下标
                int prevI = i - rollMax[j];
                //投出第i次前连续rollMax[j]的第一个下标的前一个下标
                int prevPrevI = prevI - 1;
                if (prevPrevI >= 0) {
                    //如果prevPrevI已经出现过，那么prevPrevI下标位置所有投出j的结果在第i-1下标的投次中已经被作为不合法的情况过滤掉
                    //因此prevPrevI下标位置所有非j结果在prevI位置投出j结果的话，从prevI位置开始连续投出j结果都会被认为不合法，需要被减去
                    dices[i][j] = sums[i - 1] - (sums[prevPrevI] - dices[prevPrevI][j]);
                    if (dices[i][j] < 0) {
                        //处理由于取模太小导致出现负数的情况，加回一个模就可以了
                        dices[i][j] += MOD;
                    }
                } else if (prevI >= 0) {
                    //如果prevPrevI还未到达，那么从prevI位置开始连续投出j结果都会被认为不合法，需要被减去
                    dices[i][j] = sums[i - 1] - dices[prevI][j];
                    if (dices[i][j] < 0) {
                        //处理由于取模太小导致出现负数的情况，加回一个模就可以了
                        dices[i][j] += MOD;
                    }
                } else {
                    //投出的次数还未到达rollMax[j]的大小，则前次投出的所有结果都合法
                    dices[i][j] = sums[i - 1];
                }
                sum += dices[i][j];
                sum %= MOD;
            }
            sums[i] = sum;
        }
        return (int) sums[n - 1];
    }

    /**
     * 1463【BFS+动态规划】摘樱桃 II
     */
    public int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][][] dp = new int[m][n][n]; //记录状态，第i行，robot1在j，robot2在k位置时可以摘得樱桃最大的数量
        boolean[][][] visited = new boolean[m][n][n]; //记录状态是否已经被访问过
        Queue<int[]> queue = new LinkedList<>(); //BFS的方式记录上一层已经访问的状态
        //初始化，robot1和robot2的位置以及一开始能够摘得樱桃的数量，并标记该初始状态已被访问过
        dp[0][0][n - 1] = grid[0][0] + grid[0][n - 1];
        queue.offer(new int[]{0, n - 1});
        visited[0][0][n - 1] = true;
        int i = 0, answer = 0;;
        while (!queue.isEmpty()) {
            ++i;
            if (i >= m) break; //已经走完所有层，结束循环
            int len = queue.size();
            for (int s = 0; s < len; ++s) {
                int[] prev = queue.poll();
                int pr1 = prev[0], pr2 = prev[1]; //取出上一层已访问过的状态
                for (int x = -1; x <= 1; ++x) {
                    int r1 = pr1 + x; //机器人可以向左下、下、右下三个方向移动
                    if (r1 < 0 || r1 >= n) continue; //不合法的位置不能移动
                    for (int y = -1; y <= 1; ++y) {
                        int r2 = pr2 + y;
                        if (r2 < 0 || r2 >= n) continue;
                        if (r1 == r2) { //如果两个机器人走到同一格，则这一格的樱桃只会被摘一次
                            dp[i][r1][r2] = Math.max(dp[i][r1][r2], dp[i - 1][pr1][pr2] + grid[i][r1]);
                        } else { //两个机器人不在同一格，则可以摘到不同格的樱桃的数量
                            dp[i][r1][r2] = Math.max(dp[i][r1][r2], dp[i - 1][pr1][pr2] + grid[i][r1] + grid[i][r2]);
                        }
                        answer = Math.max(answer, dp[i][r1][r2]); //当前状态可以摘得的最大樱桃数量，更新answer
                        if (!visited[i][r1][r2]) { //如果此状态第一次访问到，则加入队列中，重复访问的情况则忽略
                            queue.offer(new int[]{r1, r2});
                            visited[i][r1][r2] = true;
                        }
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 1483【倍增（动态规划）】树节点的第 K 个祖先
     */
    static class TreeAncestor {
        //dp[i][j]表示第i个数跳2^j次所到达的数，把k从二进制的角度看待，可以通过跳的2^0、2^1、2^2......2^LOG(k)组合得到跳k次的结果
        private int[][] dp;
        private int[] parent;

        public TreeAncestor(int n, int[] parent) {
            this.parent = parent;
            int LOG = 32 - Integer.numberOfLeadingZeros(n);
            dp = new int[n][LOG];
            for (int i = 0; i < n; ++i) {
                dp[i][0] = parent[i];
            }
            for (int j = 0; j < LOG - 1; ++j) {
                for (int i = 0; i < n; ++i) {
                    int p = dp[i][j];
                    dp[i][j + 1] = p < 0 ? -1 : dp[p][j];
                }
            }
        }

        public int getKthAncestor(int node, int k) {
            int m = 32 - Integer.numberOfLeadingZeros(k); // k 的二进制长度
            for (int j = 0; j < m; j++) {
                if (((k >> j) & 1) > 0) { // k 的二进制从低到高第 i 位是 1
                    node = dp[node][j];
                    if (node < 0) break;
                }
            }
            return node;
        }
    }

    /**
     * 1553【BFS+记忆化搜索】吃掉 N 个橘子的最少天数
     */
    public int minDays(int n) {
        Set<Integer> ySet = new HashSet<>();
        ySet.add(n);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        int step = 0;
        while (!queue.isEmpty()) {
            ++step;
            int len = queue.size();
            for (int i = 0; i < len; ++i) {
                Integer x = queue.poll();
                int y;
                if ((x & 1) == 0) {
                    y = x >> 1;
                    if (!ySet.contains(y)) {
                        ySet.add(y);
                        queue.offer(y);
                    }
                }
                if (x % 3 == 0) {
                    y = x / 3;
                    if (!ySet.contains(y)) {
                        ySet.add(y);
                        queue.offer(y);
                    }
                }
                if (x == 1) {
                    return step;
                }
                y = x - 1;
                if (!ySet.contains(y)) {
                    ySet.add(y);
                    queue.offer(y);
                }
            }
        }
        return -1;
    }

    //p1626
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] players = new int[n][2];
        for (int i = 0; i < n; ++i) {
            players[i][0] = scores[i];
            players[i][1] = ages[i];
        }
        //排好序，优先按分数升序排序，剩下的只要考虑球员的年龄即可
        Arrays.sort(players, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int[] dp = new int[n];
        dp[0] = players[0][0];
        int answer = dp[0];
        for (int i = 1; i < n; ++i) {
            int j = i - 1;
            while (j >= 0) {
                if (players[j][1] <= players[i][1]) {
                    //往回找，找到年龄比第i个球员小的，就是可以组队的
                    dp[i] = Math.max(dp[i], dp[j]);
                }
                --j;
            }
            dp[i] += players[i][0];
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }

    //1653
    public int minimumDeletions(String s) {
        int n = s.length();
        char[] sc = s.toCharArray();
        //0-end with a, 1-end with b
        int[][] dp = new int[n][2];
        dp[0][0] = sc[0] == 'a' ? 0 : 1;
        for (int i = 1; i < n; ++i) {
            if (sc[i] == 'b') {
                dp[i][0] = dp[i - 1][0] + 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        dp[n - 1][1] = sc[n - 1] == 'b' ? 0 : 1;
        for (int i = n - 2; i >= 0; --i) {
            if (sc[i] == 'a') {
                dp[i][1] = dp[i + 1][1] + 1;
            } else {
                dp[i][1] = dp[i + 1][1];
            }
        }
        int answer = Math.min(dp[n - 1][0], dp[0][1]);
        for (int i = 0; i < n - 1; ++i) {
            answer = Math.min(answer, dp[i][0] + dp[i + 1][1]);
        }
        return answer;
    }

    //p1664
    public int waysToMakeFair(int[] nums) {
        int result = 0;
        int total = 0;
        int normalOddSum = 0;
        int transformedOddSum = 0;
        for (int i = 0; i < nums.length; ++i) {
            total += nums[i];
            if ((i & 1) == 1) {
                transformedOddSum += nums[i];
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0) {
                if (((i - 1) & 1) == 0) {
                    normalOddSum += nums[i - 1];
                }
            }
            if ((i & 1) == 1) {
                transformedOddSum -= nums[i];
            }
            int odd = normalOddSum + transformedOddSum;
            int even = total - odd - nums[i];
            if (odd == even) ++result;
        }
        return result;
    }

    /**
     * 1745【动态规划】分割回文串 IV
     */
    public boolean checkPartitioning(String s) {
        int n = s.length();
        //预处理，先求出所有的子串是否回文，使用动态规划，从最短的开始检查，长度为1的自动是回文，长度为2的检查两个字符是否相同，长度3及以上的看两端字符是否相同结合子问题的结果判断
        boolean[][] palindrome = new boolean[n][n]; //from-to(include)
        for (int len = 1; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                if (len == 1) palindrome[i][j] = true;
                else if (len == 2) {
                    if (s.charAt(i) == s.charAt(j)) palindrome[i][j] = true;
                } else {
                    if (s.charAt(i) == s.charAt(j) && palindrome[i + 1][j - 1]) palindrome[i][j] = true;
                }
            }
        }
        //用两个标记end1和end2分割字符串为[0, end1]、[end1+1, end2]、[end2+1, n-1]三个子串
        for (int end1 = 0; end1 < n - 2; ++end1) {
            if (palindrome[0][end1]) {
                for (int end2 = end1 + 1; end2 < n - 1; ++end2) {
                    if (palindrome[end1 + 1][end2] && palindrome[end2 + 1][n - 1]) return true;
                }
            }
        }
        return false;
    }

    //p1824
    public int minSideJumps(int[] obstacles) {
        int INF = Integer.MAX_VALUE / 2;
        int n = obstacles.length;
        int[][] jumpCnt = new int[n + 1][3];
        jumpCnt[0][0] = jumpCnt[0][2] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) {
                jumpCnt[i][j] = INF;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (j != obstacles[i] - 1) {
                    jumpCnt[i][j] = Math.min(jumpCnt[i][j], jumpCnt[i - 1][j]);
                }
            }
            for (int j = 0; j < 3; ++j) {
                if (j != obstacles[i] - 1) {
                    if (j == 0) {
                        jumpCnt[i][0] = Math.min(jumpCnt[i][0], Math.min(jumpCnt[i][1] + 1, jumpCnt[i][2] + 1));
                    } else if (j == 1) {
                        jumpCnt[i][1] = Math.min(jumpCnt[i][1], Math.min(jumpCnt[i][0] + 1, jumpCnt[i][2] + 1));
                    } else {
                        jumpCnt[i][2] = Math.min(jumpCnt[i][2], Math.min(jumpCnt[i][0] + 1, jumpCnt[i][1] + 1));
                    }
                }
            }
        }
        return Arrays.stream(jumpCnt[n - 1]).min().getAsInt();
    }

    //剑指 Offer 47. 礼物的最大价值
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (m < 2) {
            int sum = 0;
            for (int val : grid[0]) {
                sum += val;
            }
            return sum;
        }
        int[] dp0 = new int[n];
        int[] dp1 = new int[n];
        dp0[0] = grid[0][0];
        dp1[0] = dp0[0] + grid[1][0];
        for (int j = 1; j < n; ++j) {
            dp0[j] = dp0[j - 1] + grid[0][j];
            dp1[j] = Math.max(dp0[j], dp1[j - 1]) + grid[1][j];
        }
        dp0 = dp1;
        for (int i = 2; i < m; ++i) {
            dp1[0] = dp0[0] + grid[i][0];
            for (int j = 1; j < n; ++j) {
                dp1[j] = Math.max(dp0[j], dp1[j - 1]) + grid[i][j];
            }
            dp0 = dp1;
        }
        return dp0[n - 1];
    }

    /**
     * 2218【动态规划+前缀和】从栈中取出 K 个硬币的最大面值和
     */
    private int[][] preSum2218;
    private Integer[][] memo2218;
    /**
     * 定义dfs(i,j)为从前i栈硬币中恰好取j个硬币，可以得到的最大面值和，使用memo缓存递归结果
     */
    private int dfs2218(int i, int j) {
        if (-1 == i) return 0;
        if (null != memo2218[i][j]) return memo2218[i][j];
        int result = dfs2218(i - 1, j); //当前栈不取硬币的情况，所有j个硬币全部都从前面的i-1栈硬币中取得
        for (int w = 0; w < Math.min(j, preSum2218[i].length); ++w) { //取到w下标的硬币的情况下会得到的最大的面值和
            result = Math.max(result, dfs2218(i - 1, j - w - 1) + preSum2218[i][w]);
        }
        memo2218[i][j] = result;
        return result;
    }
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        preSum2218 = new int[n][];
        for (int i = 0; i < n; ++i) {
            List<Integer> pile = piles.get(i);
            int prev = 0;
            int[] preSum = new int[pile.size()];
            for (int j = 0; j < pile.size(); ++j) {
                preSum[j] = prev + pile.get(j);
                prev = preSum[j];
            }
            preSum2218[i] = preSum; //前缀和的方式预处理出第i个栈取前j个硬币的面值和，后面用起来方便
        }
        memo2218 = new Integer[n][k + 1];
        int answer = dfs2218(n - 1, k); //原问题即为，从n个栈中恰好取k个硬币的最大面值和
        return answer;
    }

    /**
     * 2712【动态规划】使所有字符相等的最小成本
     */
    public long minimumCost(String s) {
        int n = s.length();
        long[] prefix = new long[n], suffix = new long[n];
        char prev = s.charAt(0);
        for (int i = 1; i < n; ++i) {
            char curr = s.charAt(i);
            if (prev == curr) {
                prefix[i] = prefix[i - 1];
            } else {
                prefix[i] = prefix[i - 1] + i;
            }
            prev = curr;
        }
        prev = s.charAt(n - 1);
        for (int i = n - 2; i >= 0; --i) {
            char curr = s.charAt(i);
            if (prev == curr) {
                suffix[i] = suffix[i + 1];
            } else {
                suffix[i] = suffix[i + 1] + (n - i - 1);
            }
            prev = curr;
        }
        long answer = Long.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            answer = Math.min(answer, prefix[i] + suffix[i]);
        }
        return answer;
    }

    /**
     * 2713【排序+记忆化搜索】矩阵中严格递增的单元格数
     */
    public int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length, answer = 1;
        int[][] dp = new int[m][n]; //其实没什么用了，但是可以在debug的时候看到结果
        int[][] sortedPoints = new int[m * n][2];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                sortedPoints[i * n + j] = new int[]{i, j};
            }
        }
        Arrays.sort(sortedPoints, Comparator.comparingInt(a -> mat[a[0]][a[1]])); //按照矩阵的值升序排序，保证访问的值是从小到大
        int[] rowMx = new int[m], colMx = new int[n]; //记忆每行和每列最大值，这样就不用每行都进行遍历。这样做的正确性在于访问的格子的值是逐个增大的，这个最大值要么适用于这个格子，要么可以叠加到这个格子上
        int r = sortedPoints[0][0], c = sortedPoints[0][1];
        int prev = mat[r][c];
        List<int[]> identicalValuePoints = new ArrayList<>(); // 存放相同数值的位置，便于后续统一处理
        identicalValuePoints.add(new int[]{r, c});
        for (int x = 1; x < m * n; ++x) {
            r = sortedPoints[x][0];
            c = sortedPoints[x][1];
            int v = mat[r][c];
            if (v != prev) {
                List<Integer> pointResults = new ArrayList<>();
                for (int[] p : identicalValuePoints) {
                    pointResults.add(Math.max(rowMx[p[0]], colMx[p[1]]) + 1);
                }
                for (int i = 0; i < identicalValuePoints.size(); ++i) {
                    int[] p = identicalValuePoints.get(i);
                    int res = pointResults.get(i);
                    dp[p[0]][p[1]] = res;
                    rowMx[p[0]] = Math.max(rowMx[p[0]], res);
                    colMx[p[1]] = Math.max(colMx[p[1]], res);
                    answer = Math.max(answer, res);
                }
                identicalValuePoints = new ArrayList<>();
                identicalValuePoints.add(new int[]{r, c});
                prev = v;
            } else {
                identicalValuePoints.add(new int[]{r, c});
            }
        }
        //最后还有一份数据，处理一下
        List<Integer> pointResults = new ArrayList<>();
        for (int[] p : identicalValuePoints) {
            pointResults.add(Math.max(rowMx[p[0]], colMx[p[1]]) + 1);
        }
        for (int i = 0; i < identicalValuePoints.size(); ++i) {
            int[] p = identicalValuePoints.get(i);
            int res = pointResults.get(i);
            dp[p[0]][p[1]] = res;
            rowMx[p[0]] = Math.max(rowMx[p[0]], res);
            colMx[p[1]] = Math.max(colMx[p[1]], res);
            answer = Math.max(answer, res);
        }
        return answer;
    }

    /**
     * 2731【脑筋急转弯+动态规划】移动机器人
     */
    public int sumDistance(int[] nums, String s, int d) {
        int mod = 1000000007;
        int n = nums.length;
        //理解此题的关键点是：将机器人碰撞看成是机器人穿透，其结果是一样的，也就是说每个机器人在d秒后到达的位置是xd=x0+R?+d:-d
        long[] endNums = new long[n];
        for (int i = 0; i < n; ++i) {
            endNums[i] = nums[i] + (s.charAt(i) == 'R' ? 1 : -1) * d;
        }
        //排序之后方便利用动态规划的方式逐步推出葱左边数起到每一个点的总的点距离
        Arrays.sort(endNums);
        long[] dp = new long[n];
        dp[1] = (endNums[1] - endNums[0]) % mod;
        for (int i = 2; i < n; ++i) {
            //左边总共i个点到第i个点的距离之和等于左边总共i-1个点到第i-1个点的距离每一个距离都加上endNums[i] - endNums[i - 1]
            dp[i] = dp[i - 1] + ((long) i * ((endNums[i] - endNums[i - 1]) % mod) % mod);
            dp[i] %= mod;
        }
        long dSum = 0;
        for (int i = 0; i < n; ++i) {
            dSum += dp[i];
            dSum %= mod;
        }
        return (int) dSum;
    }

    /**
     * 2944【动态规划】购买水果需要的最少金币数
     */
    public int minimumCoins(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int x = 0; x < n; ++x) {
            int curr = (x < 1 ? 0 : dp[x - 1]) + prices[x];
            for (int i = x; i < Math.min(n, 2 * (x + 1)); ++i) {
                dp[i] = Math.min(dp[i], curr);
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        DynamicProgrammingSolution solution = new DynamicProgrammingSolution();
        Assert.isTrue(2 == solution.minimumCost("0011"));
//        Assert.isTrue(2 == solution.minimumCoins(new int[]{1,10,1,1}));
//        Assert.isTrue(4 == solution.minimumCoins(new int[]{3,1,2}));
//        Assert.isTrue(4 == solution.minDays(10));
    }
}